package com.ronz.binarysorttree;

import com.ronz.linkedlist.util.HeroNode;

/**
 * @Description 二叉排序树
 * @Author Ronz
 * @Date 2021/1/21 18:38
 * @Version 1.0
 */
public class No1_BinarySortTree {
    public static void main(String[] args) {
        int[] arr = {7, 3, 10, 12, 5, 1, 9, 11};
        BinarySortTree tree = new BinarySortTree(null);
        for (int item : arr){
            tree.addNode(tree.new Node(item));  // 添加节点
        }
        tree.infixOrder();  // 中序遍历

        BinarySortTree.Node node = tree.searchNode(2);

        // 删除节点
        System.out.println("========= 删除节点 ==========");
        tree.deleteBST(3);

        tree.infixOrder();
        System.out.println();

    }
}

class BinarySortTree{

    private Node root;  // 根节点

    public BinarySortTree(Node node){
        this.root = node;
    }
    // 添加节点到二叉排序树中
    public void addNode(Node node){
        if (root == null){
            root = node;
        }else{
            root.addNode(node);
        }
    }
    // 中序遍历：左根右
    public void infixOrder(){
        if (root != null){
            root.infixOrder();
        }
    }
    // 查找指定节点
    public Node searchNode(int key){
        return root.searchNode(key);
    }
    // 删除指定节点
    public void deleteBST(int key){
        if (root != null){
            if (root.value == key){ // 如果目标节点是根节点，直接删除
                root = null;
            }else{  // 如果不是根节点，就调用删除方法
                root.deleteBST(key);
            }
        }
    }

    /**
     * 节点
     */
    class Node{
        int value;  // 节点的值
        Node left;  // 指向左子节点
        Node right; // 指向右子节点

        public Node(int value){
            this.value = value;
        }
        // 添加节点到二叉排序树中
        public void addNode(Node node){
            if (node != null){
                if (node.value >= this.value){ // 如果大于当前节点的值
                    if (this.right != null){    // 如果当前节点存在右子节点
                        this.right.addNode(node);
                    }else{
                        this.right = node;
                    }
                }else{
                    if (this.left != null){ // 如果小于当前节点的值
                        this.left.addNode(node);
                    }else{
                        this.left = node;
                    }
                }
            }
        }
        // 中序遍历二叉排序树：根->左->右
        public void infixOrder(){
            System.out.println(this);   // 根
            if (this.left != null){     // 左子节点
                this.left.infixOrder();
            }
            if (this.right != null){    // 右子节点
                this.right.infixOrder();
            }
        }

        /**
         * 查找指定节点
         * @param key   指定节点的值
         */
        public Node searchNode(int key) {
            if (this.value == key) {    // 首先判断是否是本节点
                return this;
            } else {
                if (this.value > key) { // 如果小于本节点，向左递归
                    if (this.left != null) {    // 如果左节点存在才递归
                        return this.left.searchNode(key);
                    }
                }else{  // 不是小于，就是大于本节点，向右递归
                    if (this.right != null) {   // 右节点存在才递归
                        return this.right.searchNode(key);
                    }
                }
                return null;
            }
        }

        /**
         * 查找指定节点的父节点
         * @param key   指定节点的值
         */
        public Node searchParentNode(int key){
            if ((this.left !=null && this.left.value == key) ||
                    (this.right != null && this.right.value == key)){ // 如果当前节点的某个子节点是目标节点
                return this;    // 返回当前节点
            }else{
                if (key < this.value && this.left != null){  // 如果目标值小于当前节点
                    return this.left.searchParentNode(key);
                }else if (key > this.value && this.right != null){  // 如果目标值大于当前节点
                    return this.right.searchParentNode(key);
                }else{
                    return null;
                }
            }
        }

        /**
         * 删除节点
         * @param key 待删除节点的值
         */
        public boolean deleteBST(int key){
            if (this.value == key){ // 如果等于当前节点，就执行删除节点操作
                deleteNode(root, key);  // 执行删除操作
                return true;
            }else{
                if (key < this.value && this.left != null){  // 如果目标值小于当前节点，就向左子树递归查找
                    return this.left.deleteBST(key);
                }else if (key > this.value && this.right != null){  // 如果大于当前节点，就向右子树递归查找
                    return this.right.deleteBST(key);
                }else{
                    return false;
                }
            }
        }

        /**
         * 删除节点的操作过程
         * @param root  根节点
         * @param key   待删除节点的值
         */
        public void deleteNode(Node root, int key){
            Node targetNode = root.searchNode(key);  // 首先找到要删除的节点
            if (targetNode != null){
                Node parentNode = root.searchParentNode(key);   // 找到待删除节点的父节点
                if (targetNode.left == null &&  targetNode.right == null){  // 情况一：目标是一个叶子节点
                    if (parentNode.left.value == key){  // 判断目标节点是父节点的左子节点还是右子节点
                        parentNode.left = null; // 直接删除即可
                    }else{
                        parentNode.right = null;
                    }
                }else if (targetNode.left != null && targetNode.right != null){ // 情况二：目标节点有两个子树
                    /* 找出目标节点右子树中的最小值 */
                    Node rightTreeNode = targetNode.right;  // 获取目标节点的右子节点
                    if (rightTreeNode.left == null){       // 如果右子节点没有左子树，说明右子节点就是最小节点
                        targetNode.value = rightTreeNode.value; // 将最小节点复制到目标结点
                        targetNode.right = null;    // 删除最小节点
                    }else{  // 如果目标节点的右子节点有左子树，就往下找
                        while (rightTreeNode.left.left != null){    // 因为要删除最小节点，所以要找最小节点的父节点
                            rightTreeNode = rightTreeNode.left;
                        }
                        targetNode.value = rightTreeNode.left.value;
                        rightTreeNode.left = null;
                    }

                }else{  // 情况三：目标节点只有一个子树
                    if (targetNode.left != null){   // 如果目标节点只有左子树

                        if (parentNode.left != null && parentNode.left.value == key){  // 如果目标节点是父节点的左子树
                            parentNode.left = targetNode.left;  // 让父节点的左指针指向目标节点的左子树
                        }else if (parentNode.right != null && parentNode.right.value == key){  // 如果目标节点是父节点的右子树
                            parentNode.right = targetNode.left; // 让父节点的右指针指向目标节点左子树
                        }
                    }else{  // 如果目标节点只有右子树
                        if (parentNode.left != null && parentNode.left.value == key){  // 如果目标节点是父节点的左子树
                            parentNode.left = targetNode.right;
                        }else if (parentNode.right != null && parentNode.right.value == key){  // 如果目标节点是父节点的右子树
                            parentNode.right = targetNode.right;
                        }
                    }
                }
            }
        }
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    }
}
